# @Time    :2025/4/10 9:30
def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for j in range(gap, n):  # 控制所有子序列的所有元素
            i = j
            while i > 0:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap

                else:
                    break
      #每次执行完 缩短gap步长
        gap//=2


if __name__ == '__main__':
    alist = [54, 16, 93, 37, 77, 1, 44, 95, 20]
    print(alist)
    shell_sort(alist)
    print(alist)
